\chapter{搜索}

\section{人工智能}

\subsection{人工智能（Artificial Intelligence）}

我们称自己为智人，几千年来，我们一直试图了解我们是如何思考和行动的。\\

AI企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人学、语言识别、图像识别、自然语言处理和专家系统等。\\

人类通过器官（眼、耳、鼻、口、皮肤）从外部环境进行感知，并做出一系列行为（说话、吃饭、移动、决策等）。\\

智能Agent通过传感器（麦克风、摄像头、陀螺仪、声呐等）从外部环境进行感知，从而进行规划、分类、预测等行为。\\

一个理性的Agent（Rational Agent）需要能进行理性的思考和行为，即在现有环境下，做出利益最大化的行为。\\

\subsection{AI的演变}

\subsubsection{基于逻辑的AI（Logic-Based AI）}

最初的人工智能是基于逻辑学的，数理逻辑的思想和方法一直在知识表示中发挥着重要作用。基于逻辑的AI的领域包括常识推理、溯因推理、归纳推理、计算逻辑、概率、规划、决策等。\\

建立在命题逻辑和谓词逻辑上的AI在九十年代前进入了寒冬，直到大量统计学方法引入之后才有了现在大热的机器学习。\\

\subsubsection{专家系统（Expert System）}

专家系统是一个智能计算机程序，其内部含有大量的某个领域专家水平的知识与经验，它根据系统中的知识与经验，进行推理和判断，模拟人类专家的决策过程，以便解决那些需要人类专家处理的复杂问题。\\

例如医疗诊断系统，它依靠病人的具体病况作为条件来分析，系统可根据病人的病情描述，在已有的知识与经验中，匹配最有可能的病症和治疗方案。\\

虽然专家系统看起来已经发展了很久，但是它并没有那么可靠。例如在实际的看病过程中，往往医生在除了问询之外，还有自己做推断的部分，目前的专家系统还没有办法做到对病人的病况了解的足够清晰。\\

其次专家系统的一大问题就是其潜在的风险性，包括无人驾驶汽车也有类似的问题。在发生问题之后，谁来背负责任呢？比如某患者采用了一个医疗专家系统，然后听从专家系统的指示，可结果病情却越来越重。\\

\subsubsection{机器学习（Machine Learning）}

机器学习是一门多领域交叉的学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科，专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。\\

例如在自动驾驶中需要通过机器视觉不断看到周围的物体，然后通过机器学习来辨识出这些物体是什么（人、车、交通灯等）。学会辨识图片的过程需要输入大量的车辆的图片给机器学习，最后它就会知道这些图片代表的是车。

\begin{figure}[H]
    \centering
    \includegraphics{img/Chapter1/1-1/1.png}
    \caption{自动驾驶}
\end{figure}

机器学习最重要的是预测，比如通过大量的图片学会什么是车后，再来一张没有见过的车辆的图片，我们希望机器可以做出正确的判断。因此机器学习包含训练和预测两个部分，并且要保证一定的正确率。\\

\subsubsection{深度学习（Deep Learning）}

深度学习是一种深层次的学习，以教儿童认字为例，按照字从简单到复杂的顺序，让儿童反复看每个字的各种写法，并自己临摹。看得多了，自然就记住了。下次再见到同一个字，就很容易能认出来。认字时，一定是儿童的大脑在接受许多遍相似图像的刺激后，为每个字总结出了某种规律性的东西，下次大脑再看到符合这种规律的图案，就知道是什么字了。\\

计算机在识别时，也要先把每一个图案反复看很多很多遍，然后在总结出一个规律，以后计算机再看到类似的图案，只要符合之前总结的规律，计算机就能知道这是什么图案。用专业的术语来说，计算机用来学习的、反复看的图片叫训练数据集。

\begin{figure}[H]
    \centering
    \includegraphics[scale=0.5]{img/Chapter1/1-1/2.png}
    \caption{验证码}
\end{figure}

深度学习与机器学习的主要区别是在于性能。当数据量很少的时候，深度学习的性能并不好，因为深度学习算法需要大量数据才能很好理解其中蕴含的模式。因此深度学习算法严重依赖高端机，而传统的机器学习算法在低端机上就能运行。深度学习需要GPU（Graphics Processing Unit）进行大量的矩阵乘法运算。

\newpage

\section{状态空间}

\subsection{智能Agent}

智能Agent的设计取决于一系列因素：

\begin{itemize}
    \item 环境：静态（static）、动态（dynamic）
    \item 表示方案（representation scheme）：状态（state）、特征（feature）、关系（relation）
    \item 可观察性（observability）：完全可观察、部分可观察
    \item 参数类型：离散（discrete）、连续（continuous）
    \item 不确定性（uncertainty）：确定性（deterministic）、随机性（stochastic）
    \item 学习：知识是给定的（已知的），知识是学来的（未知的）
    \item Agent数量：单Agent、多Agent
\end{itemize}

\vspace{0.5cm}

\subsection{状态空间（State Space）}

假设有两个有灰尘的房间A和B，吸尘器一开始位于房间A，吸尘器只能进行左移、右移和吸尘三个操作，最终的目标是将两个房间内的灰尘清扫完毕。\\

因此根据房间有无灰尘和吸尘器的位置，一共存在8种状态。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \draw (0,2) rectangle (2,3);
        \draw[-] (1,2) -- (1,3) node[above] {State 1};
        \draw (3,2) rectangle (5,3);
        \draw[-] (4,2) -- (4,3) node[above] {State 2};
        \draw (6,2) rectangle (8,3);
        \draw[-] (7,2) -- (7,3) node[above] {State 3};
        \draw (9,2) rectangle (11,3);
        \draw[-] (10,2) -- (10,3) node[above] {State 4};

        \draw (0,0) rectangle (2,1);
        \draw[-] (1,0) -- (1,1) node[above] {State 5};
        \draw (3,0) rectangle (5,1);
        \draw[-] (4,0) -- (4,1) node[above] {State 6};
        \draw (6,0) rectangle (8,1);
        \draw[-] (7,0) -- (7,1) node[above] {State 7};
        \draw (9,0) rectangle (11,1);
        \draw[-] (10,0) -- (10,1) node[above] {State 8};

        % State 1
        \draw[thick, -] (0.3,2.8) -- (0.7,2.8) -- (0.8,2.6) -- (0.2,2.6) -- (0.3,2.8);
        \draw[thick] (0.4,2.55) circle (0.05);
        \draw[thick] (0.6,2.55) circle (0.05);

        \draw[fill=gray] (0.3,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (0.5,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (0.7,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (0.4,2.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (0.6,2.1) ellipse (0.025 and 0.05);

        \draw[fill=gray] (1.3,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (1.5,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (1.7,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (1.4,2.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (1.6,2.1) ellipse (0.025 and 0.05);

        % State 2
        \draw[thick, -] (4.3,2.8) -- (4.7,2.8) -- (4.8,2.6) -- (4.2,2.6) -- (4.3,2.8);
        \draw[thick] (4.4,2.55) circle (0.05);
        \draw[thick] (4.6,2.55) circle (0.05);

        \draw[fill=gray] (3.3,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (3.5,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (3.7,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (3.4,2.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (3.6,2.1) ellipse (0.025 and 0.05);

        \draw[fill=gray] (4.3,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (4.5,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (4.7,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (4.4,2.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (4.6,2.1) ellipse (0.025 and 0.05);

        % State 3
        \draw[thick, -] (6.3,2.8) -- (6.7,2.8) -- (6.8,2.6) -- (6.2,2.6) -- (6.3,2.8);
        \draw[thick] (6.4,2.55) circle (0.05);
        \draw[thick] (6.6,2.55) circle (0.05);

        \draw[fill=gray] (7.3,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (7.5,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (7.7,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (7.4,2.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (7.6,2.1) ellipse (0.025 and 0.05);

        % State 4
        \draw[thick, -] (10.3,2.8) -- (10.7,2.8) -- (10.8,2.6) -- (10.2,2.6) -- (10.3,2.8);
        \draw[thick] (10.4,2.55) circle (0.05);
        \draw[thick] (10.6,2.55) circle (0.05);

        \draw[fill=gray] (10.3,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (10.5,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (10.7,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (10.4,2.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (10.6,2.1) ellipse (0.025 and 0.05);

        % State 5
        \draw[thick, -] (0.3,0.8) -- (0.7,0.8) -- (0.8,0.6) -- (0.2,0.6) -- (0.3,0.8);
        \draw[thick] (0.4,0.55) circle (0.05);
        \draw[thick] (0.6,0.55) circle (0.05);

        % State 6
        \draw[thick, -] (4.3,0.8) -- (4.7,0.8) -- (4.8,0.6) -- (4.2,0.6) -- (4.3,0.8);
        \draw[thick] (4.4,0.55) circle (0.05);
        \draw[thick] (4.6,0.55) circle (0.05);

        % State 7
        \draw[thick, -] (6.3,0.8) -- (6.7,0.8) -- (6.8,0.6) -- (6.2,0.6) -- (6.3,0.8);
        \draw[thick] (6.4,0.55) circle (0.05);
        \draw[thick] (6.6,0.55) circle (0.05);

        \draw[fill=gray] (6.3,0.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (6.5,0.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (6.7,0.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (6.4,0.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (6.6,0.1) ellipse (0.025 and 0.05);

        % State 8
        \draw[thick, -] (10.3,0.8) -- (10.7,0.8) -- (10.8,0.6) -- (10.2,0.6) -- (10.3,0.8);
        \draw[thick] (10.4,0.55) circle (0.05);
        \draw[thick] (10.6,0.55) circle (0.05);

        \draw[fill=gray] (9.3,0.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (9.5,0.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (9.7,0.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (9.4,0.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (9.6,0.1) ellipse (0.025 and 0.05);
    \end{tikzpicture}
\end{figure}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|}
            \hline
            \textbf{状态} & \textbf{房间A} & \textbf{房间B} & \textbf{吸尘器位置} \\
            \hline
            1             & 脏             & 脏             & A                   \\
            \hline
            2             & 脏             & 脏             & B                   \\
            \hline
            3             & 干净           & 脏             & A                   \\
            \hline
            4             & 干净           & 脏             & B                   \\
            \hline
            5             & 干净           & 干净           & A                   \\
            \hline
            6             & 干净           & 干净           & B                   \\
            \hline
            7             & 脏             & 干净           & A                   \\
            \hline
            8             & 脏             & 干净           & B                   \\
            \hline
        \end{tabular}
    }
\end{table}

假设以状态6作为目标状态（goal state），可以得到状态空间图：\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        % Row 1
        \draw (-3,2) rectangle (-1,3);
        \draw[-] (-2,2) -- (-2,3);
        \draw (1,2) rectangle (3,3);
        \draw[-] (2,2) -- (2,3);

        \draw[thick, -] (-2.3,2.8) -- (-2.7,2.8) -- (-2.8,2.6) -- (-2.2,2.6) -- (-2.3,2.8);
        \draw[thick] (-2.4,2.55) circle (0.05);
        \draw[thick] (-2.6,2.55) circle (0.05);

        \draw[fill=gray] (-2.3,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-2.5,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-2.7,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-2.4,2.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (-2.6,2.1) ellipse (0.025 and 0.05);

        \draw[fill=gray] (-1.3,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-1.5,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-1.7,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-1.4,2.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (-1.6,2.1) ellipse (0.025 and 0.05);

        \draw[thick, -] (2.3,2.8) -- (2.7,2.8) -- (2.8,2.6) -- (2.2,2.6) -- (2.3,2.8);
        \draw[thick] (2.4,2.55) circle (0.05);
        \draw[thick] (2.6,2.55) circle (0.05);

        \draw[fill=gray] (1.3,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (1.5,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (1.7,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (1.4,2.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (1.6,2.1) ellipse (0.025 and 0.05);

        \draw[fill=gray] (2.3,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (2.5,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (2.7,2.2) ellipse (0.05 and 0.025);
        \draw[fill=gray] (2.4,2.1) ellipse (0.025 and 0.05);
        \draw[fill=gray] (2.6,2.1) ellipse (0.025 and 0.05);

        \draw[->] (-1,2.75) -- (0,2.75) node[above] {R} -- (1,2.75);
        \draw[<-] (-1,2.25) -- (0,2.25) node[below] {L} -- (1,2.25);

        \draw[->] (-3,2.75) arc (90:270:3mm) node[xshift=-0.25cm, yshift=0.25cm, left] {L};
        \draw[->] (3,2.75) arc (90:-90:3mm) node[xshift=0.25cm, yshift=0.25cm, right] {R};

        \draw[->] (-2,2) -- (-6,0.5) node[xshift=2.5cm, yshift=0.75cm, right] {S};
        \draw[->] (2,2) -- (6,0.5) node[xshift=-2.5cm, yshift=0.75cm, left] {S};

        % Row 2
        \draw (-7,-0.5) rectangle (-5,0.5);
        \draw[-] (-6,-0.5) -- (-6,0.5);
        \draw (-3,-0.5) rectangle (-1,0.5);
        \draw[-] (-2,-0.5) -- (-2,0.5);
        \draw (1,-0.5) rectangle (3,0.5);
        \draw[-] (2,-0.5) -- (2,0.5);
        \draw (5,-0.5) rectangle (7,0.5);
        \draw[-] (6,-0.5) -- (6,0.5);

        \draw[thick, -] (-6.3,0.3) -- (-6.7,0.3) -- (-6.8,0.1) -- (-6.2,0.1) -- (-6.3,0.3);
        \draw[thick] (-6.4,0.05) circle (0.05);
        \draw[thick] (-6.6,0.05) circle (0.05);

        \draw[fill=gray] (-5.3,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-5.5,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-5.7,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-5.4,-0.4) ellipse (0.025 and 0.05);
        \draw[fill=gray] (-5.6,-0.4) ellipse (0.025 and 0.05);

        \draw[thick, -] (-1.3,0.3) -- (-1.7,0.3) -- (-1.8,0.1) -- (-1.2,0.1) -- (-1.3,0.3);
        \draw[thick] (-1.4,0.05) circle (0.05);
        \draw[thick] (-1.6,0.05) circle (0.05);

        \draw[fill=gray] (-1.3,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-1.5,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-1.7,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (-1.4,-0.4) ellipse (0.025 and 0.05);
        \draw[fill=gray] (-1.6,-0.4) ellipse (0.025 and 0.05);

        \draw[thick, -] (1.3,0.3) -- (1.7,0.3) -- (1.8,0.1) -- (1.2,0.1) -- (1.3,0.3);
        \draw[thick] (1.4,0.05) circle (0.05);
        \draw[thick] (1.6,0.05) circle (0.05);

        \draw[fill=gray] (1.3,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (1.5,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (1.7,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (1.4,-0.4) ellipse (0.025 and 0.05);
        \draw[fill=gray] (1.6,-0.4) ellipse (0.025 and 0.05);

        \draw[thick, -] (6.3,0.3) -- (6.7,0.3) -- (6.8,0.1) -- (6.2,0.1) -- (6.3,0.3);
        \draw[thick] (6.4,0.05) circle (0.05);
        \draw[thick] (6.6,0.05) circle (0.05);

        \draw[fill=gray] (5.3,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (5.5,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (5.7,-0.3) ellipse (0.05 and 0.025);
        \draw[fill=gray] (5.4,-0.4) ellipse (0.025 and 0.05);
        \draw[fill=gray] (5.6,-0.4) ellipse (0.025 and 0.05);

        \draw[->] (-5,0.25) -- (-4,0.25) node[above] {R} -- (-3,0.25);
        \draw[<-] (-5,-0.25) -- (-4,-0.25) node[below] {L} -- (-3,-0.25);

        \draw[->] (-7,0.25) arc (90:270:3mm) node[xshift=-0.25cm, yshift=0.25cm, left] {L};
        \draw[->] (-1,0.25) arc (90:-90:3mm) node[xshift=0.25cm, yshift=0.25cm, right] {R};
        \draw[->] (-5.75,-0.5) arc (0:-180:4mm) node[xshift=0.1cm, yshift=-0.75cm, right] {S};

        \draw[->] (3,0.25) -- (4,0.25) node[above] {R} -- (5,0.25);
        \draw[<-] (3,-0.25) -- (4,-0.25) node[below] {L} -- (5,-0.25);

        \draw[->] (1,0.25) arc (90:270:3mm) node[xshift=-0.25cm, yshift=0.25cm, left] {L};
        \draw[->] (7,0.25) arc (90:-90:3mm) node[xshift=0.25cm, yshift=0.25cm, right] {R};
        \draw[->] (6.25,-0.5) arc (0:-180:4mm) node[xshift=0.1cm, yshift=-0.75cm, right] {S};

        \draw[->] (-2,-0.5) -- (2,-2) node[xshift=-3cm, yshift=1cm, left] {S};
        \draw[<-] (2,-0.5) -- (-2,-2) node[xshift=3cm, yshift=1cm, right] {S};

        % Row 3
        \draw (-3,-3) rectangle (-1,-2);
        \draw[-] (-2,-3) -- (-2,-2);
        \draw (1,-3) rectangle (3,-2);
        \draw[-] (2,-3) -- (2,-2);

        \draw[thick, -] (-2.3,-2.2) -- (-2.7,-2.2) -- (-2.8,-2.4) -- (-2.2,-2.4) -- (-2.3,-2.2);
        \draw[thick] (-2.4,-2.45) circle (0.05);
        \draw[thick] (-2.6,-2.45) circle (0.05);

        \draw[thick, -] (2.3,-2.2) -- (2.7,-2.2) -- (2.8,-2.4) -- (2.2,-2.4) -- (2.3,-2.2);
        \draw[thick] (2.4,-2.45) circle (0.05);
        \draw[thick] (2.6,-2.45) circle (0.05);

        \draw[->] (-1,-2.25) -- (0,-2.25) node[above] {R} -- (1,-2.25);
        \draw[<-] (-1,-2.75) -- (0,-2.75) node[below] {L} -- (1,-2.75);

        \draw[->] (-3,-2.25) arc (90:270:3mm) node[xshift=-0.25cm, yshift=0.25cm, left] {L};
        \draw[->] (3,-2.25) arc (90:-90:3mm) node[xshift=0.25cm, yshift=0.25cm, right] {R};

        \draw[->] (-1.75,-3) arc (0:-180:4mm) node[xshift=0.1cm, yshift=-0.75cm, right] {S};
        \draw[->] (2.25,-3) arc (0:-180:4mm) node[xshift=0.1cm, yshift=-0.75cm, right] {S};
    \end{tikzpicture}
\end{figure}

提取问题中的特征：

\begin{itemize}
    \item $ status = \{clean, dirty\} $
    \item $ location = \{A, B\} $
    \item $ actions = \{suck, left, right\} $
\end{itemize}

吸尘器的处理过程可以表示为：

\begin{algorithm}[H]
    \caption{VacuumCleaner}
    \begin{algorithmic}[1]
        \Procedure{VacuumCleaner}{status, location}
        \If {status = dirty}
        \State \Return suck
        \EndIf

        \If {location = A and status = clean}
        \State \Return right
        \EndIf

        \If {location = B and status = clean}
        \State \Return left
        \EndIf
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\vspace{0.5cm}

\subsection{性能评估（Performance Measure）}

算法的性能评估包含以下几个方面：

\begin{itemize}
    \item 完备性（completeness）
          \begin{itemize}
              \item 完备（Complete）：算法可以到达目标状态
              \item 不完备（incomplete）：算法无法到达目标状态
          \end{itemize}
    \item 正确性
    \item 最优性（optimality）：算法以最优解（最小代价）找到到达目标状态的路径
    \item 时间复杂度（time complexity）：求解所需的时间
    \item 空间复杂度（space complexity）：求解所需的存储空间
\end{itemize}

\newpage

\section{盲目搜索/无信息搜索}

\subsection{盲目搜索/无信息搜索（Uninformed Search）}

当需要采取的正确行动不是显而易见时，Agent就需要提前规划，考虑能够通往目标状态的一系列行动，Agent所进行的计算过程被称为搜索。\\

对于一个问题，首先需要确定它的初始状态（initial state）和目标状态，其次需要对问题进行建模（modeling）。一个问题的建模包括6个部分：

\begin{enumerate}
    \item 状态集合
    \item 初始状态
    \item 行为集合$ Actions(s) $：在状态$ s $时所有合法的行为集合
    \item 状态转移$ Result(s, a) $：返回在状态$ s $时执行行为$ a $后的状态
    \item 目标状态：使用$ IsGoal(s) $来判断状态$ s $是否为目标状态
    \item 行为代价函数（Action Cost Function）：在某个状态执行某个行为所需的代价，使用$ ActionCost(s, a, s') $表示在状态$ s $执行行为$ a $到达状态$ s' $所需的代价
\end{enumerate}

在八数码（8-puzzle）问题中，在一个3*3的方格中，有数字1~8和一个空白，最终需要将数字依次排列，使空白位于最后的位置。\\

八数码问题一共存在$ 9! = 362880 $种状态，其中初始状态为任意一种摆放布局，目标状态为依次排列的布局。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \node at (1.5,3.5) {State 1};
        \draw (0,0) rectangle (3,3);
        \draw[-] (0,1) -- (3,1);
        \draw[-] (0,2) -- (3,2);
        \draw[-] (1,0) -- (1,3);
        \draw[-] (2,0) -- (2,3);

        \node at (0.5,2.5) {2};
        \node at (1.5,2.5) {7};
        \node at (2.5,2.5) {4};
        \node at (0.5,1.5) {5};
        \node at (2.5,1.5) {8};
        \node at (0.5,0.5) {3};
        \node at (1.5,0.5) {1};
        \node at (2.5,0.5) {6};

        \node at (5.5,3.5) {State 2};
        \draw (4,0) rectangle (7,3);
        \draw[-] (4,1) -- (7,1);
        \draw[-] (4,2) -- (7,2);
        \draw[-] (5,0) -- (5,3);
        \draw[-] (6,0) -- (6,3);

        \node at (4.5,2.5) {2};
        \node at (5.5,2.5) {7};
        \node at (6.5,2.5) {4};
        \node at (5.5,1.5) {5};
        \node at (6.5,1.5) {8};
        \node at (4.5,0.5) {3};
        \node at (5.5,0.5) {1};
        \node at (6.5,0.5) {6};

        \node at (8,1.5) {......};

        \node at (10.5,3.5) {State 362880};
        \draw (9,0) rectangle (12,3);
        \draw[-] (9,1) -- (12,1);
        \draw[-] (9,2) -- (12,2);
        \draw[-] (10,0) -- (10,3);
        \draw[-] (11,0) -- (11,3);

        \node at (9.5,2.5) {1};
        \node at (10.5,2.5) {2};
        \node at (11.5,2.5) {3};
        \node at (9.5,1.5) {4};
        \node at (10.5,1.5) {5};
        \node at (11.5,1.5) {6};
        \node at (9.5,0.5) {7};
        \node at (10.5,0.5) {8};
    \end{tikzpicture}
\end{figure}

行为包括可以将空白进行上移（U）、下移（D）、左移（L）、右移（R），每次移动的代价可以认为都为1，例如对初始状态中的空白进行左移，其状态转移可表示为$ s_2 = Result(s_1, L) $。\\

在罗马尼亚地图（Romania map）中，例如初始位置位于Arad，最终想要到达Bucharest。问题的状态为所有的城市，每次行动的代价为城市见的距离。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \draw[fill=brown] (0,0) rectangle (0.3,0.3) node[above] {Fagaras};
        \draw[fill=brown] (-3,0) rectangle (-2.7,0.3) node[above] {Sibiu};
        \draw[fill=brown] (-4,4) rectangle (-3.7,4.3) node[above] {Oradea};
        \draw[fill=brown] (-5,3) node[left] {Zerind} rectangle (-4.7,3.3);
        \draw[fill=brown] (-6,2) node[left] {Arad} rectangle (-5.7,2.3);
        \draw[fill=brown] (-6,-2) node[left] {Timisoara} rectangle (-5.7,-1.7);
        \draw[fill=brown] (-5,-3) node[left] {Lugoj} rectangle (-4.7,-2.7);
        \draw[fill=brown] (-5,-5) node[left] {Mehadia} rectangle (-4.7,-4.7);
        \draw[fill=brown] (-5,-7) node[left] {Drobeta} rectangle (-4.7,-6.7);
        \draw[fill=brown] (-2,-2) node[left] {Rimnicu Vilcea} rectangle (-1.7,-1.7);
        \draw[fill=brown] (0,-4) rectangle (0.3,-3.7) node[above] {Pitesti};
        \draw[fill=brown] (-1,-7) node[below] {Craiova} rectangle (-0.7,-6.7);
        \draw[fill=brown] (3,-5) node[left] {Bucharest} rectangle (3.3,-4.7);
        \draw[fill=brown] (2,-7) node[below] {Giurgiu} rectangle (2.3,-6.7);
        \draw[fill=brown] (4,-4) node[left] {Urziceni} rectangle (4.3,-3.7);
        \draw[fill=brown] (6,-4) rectangle (6.3,-3.7) node[above] {Hirsova};
        \draw[fill=brown] (7,-6) node[below] {Eforie} rectangle (7.3,-5.7);
        \draw[fill=brown] (5,0) rectangle (5.3,0.3) node[right] {Vaslui};
        \draw[fill=brown] (4,3) rectangle (4.3,3.3) node[above] {Iasi};
        \draw[fill=brown] (2,5) rectangle (2.3,5.3) node[above] {Neamt};

        \draw[-] (0,0.15) -- (-1.35,0.15) node[above] {99} -- (-2.7,0.15);
        \draw[-] (-3,0.15) -- (-3.7,4) node[xshift=0.5cm, yshift=-2cm, right] {151};
        \draw[-] (-4,4) -- (-4.7,3.3) node[yshift=0.5cm, left] {71};
        \draw[-] (-5,3) -- (-5.7,2.3) node[xshift=0.5cm, yshift=0.2cm, right] {75};
        \draw[-] (-5.7,2.3) -- (-3,0.15) node[xshift=-2cm, yshift=0.7cm, above] {140};
        \draw[-] (-5.85,2) -- (-5.85,-1.7) node[yshift=2cm, left] {118};
        \draw[-] (-5.7,-2) -- (-5,-2.75) node[xshift=-0.5cm, yshift=0.2cm, left] {111};
        \draw[-] (-4.85,-3) -- (-4.85,-4.7) node[yshift=0.5cm, left] {70};
        \draw[-] (-4.85,-5) -- (-4.85,-6.7) node[yshift=0.5cm, left] {75};
        \draw[-] (-4.7,-6.85) -- (-1,-6.85) node[xshift=-2cm, below] {120};
        \draw[-] (-2.7,0) -- (-2,-1.7) node[xshift=-0.2cm, yshift=0.6cm, left] {80};
        \draw[-] (-1.8,-2) -- (-0.8,-6.7) node[xshift=-0.5cm, yshift=2cm, left] {146};
        \draw[-] (-0.8,-6.7) -- (0,-4) node[xshift=-0.5cm, yshift=-1.5cm, right] {138};
        \draw[-] (-1.8,-2) -- (0,-3.7) node[xshift=-1cm, yshift=0.8cm, below] {97};
        \draw[-] (0.3,-4) -- (3,-4.8) node[xshift=-1.5cm, yshift=0.5cm, below] {101};
        \draw[-] (3,-4.8) -- (0.3,0) node[xshift=1cm, yshift=-2cm, left] {211};
        \draw[-] (3,-5) -- (2.3,-6.7) node[xshift=0.4cm, yshift=0.8cm, right] {90};
        \draw[-] (3.3,-4.7) -- (4,-4) node[below] {85};
        \draw[-] (4.3,-3.85) -- (6,-3.85) node[xshift=-1cm, below] {98};
        \draw[-] (6.3,-4) -- (7,-5.7) node[xshift=-0.4cm, yshift=0.8cm, left] {86};
        \draw[-] (4.3,-3.7) -- (5,0) node[xshift=-0.3cm, yshift=-2cm, right] {142};
        \draw[-] (5,0.3) -- (4.3,3) node[xshift=0.5cm, yshift=-1.5cm, left] {92};
        \draw[-] (4,3.3) -- (2.3,5) node[xshift=0.8cm, yshift=-1cm, below] {87};
    \end{tikzpicture}
    \caption{罗马尼亚地图}
\end{figure}

\vspace{0.5cm}

\subsection{搜索树（Search Tree）}

搜索树中的每个结点对应于状态空间中的一个状态，边对应着行为，根结点对应于初始状态。搜索树从根结点开始，每次选择一个结点进行扩展（expand），扩展的过程是递归的，直到搜索到目标结点。\\

搜索树中的每个结点由4部分组成：

\begin{enumerate}
    \item node.State：状态信息（如Sibiu）
    \item node.Parent：父结点（如Arad），用于回溯
    \item node.Action：从父结点到当前结点的行为（如ToSibiu）
    \item node.PathCost：从根结点到当前结点的代价，用于查找最优解
\end{enumerate}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[
            level distance=1.5cm,
            level 1/.style={sibling distance=5cm},
            level 2/.style={sibling distance=3cm},
            level 3/.style={sibling distance=2cm},
            level 4/.style={sibling distance=1cm}
        ]
        \node[circle,draw,fill=green] {}
        child {
                node[circle,draw,fill=brown] {}
            }
        child {
                node[circle,draw,fill=brown] {}
                child {
                        node[circle,draw,fill=brown] {}
                    }
                child {
                        node[circle,draw,fill=brown] {}
                        child {node[circle,draw,fill=brown] {}}
                        child {node[circle,draw,fill=red] {}}
                        child {
                                node[circle,draw,fill=brown] {}
                                child {
                                        node[circle,draw,fill=red] {}
                                        child {node[circle,draw,fill=gray] {}}
                                    }
                            }
                    }
                child {
                        node[circle,draw,fill=brown] {}
                        child {
                                node[circle,draw,fill=red] {}
                                child {
                                        node[circle,draw,fill=gray] {}
                                        child {node[circle,draw,fill=gray] {}}
                                    }
                            }
                    }
            }
        child {
                node[circle,draw,fill=brown] {}
                child {
                        node[circle,draw,fill=brown] {}
                        child {
                                node[circle,draw,fill=red] {}
                                child {
                                        node[circle,draw,fill=gray] {}
                                        child {node[circle,draw,fill=gray] {}}
                                    }
                                child {
                                        node[circle,draw,fill=gray] {}
                                        child {node[circle,draw,fill=gray] {}}
                                    }
                            }
                    }
            };

        \node at (0,0.5) {Start Node};
        \node at (-4.5,-2) {Reached Nodes};
        \node at (0,-5) {Frontier Nodes};
        \node at (0,-7.5) {Unexplored Nodes};
    \end{tikzpicture}
    \caption{搜索树}
\end{figure}

\begin{algorithm}[H]
    \caption{Expand a node}
    \begin{algorithmic}[1]
        \Procedure{Expand}{problem, node} yield nodes
        \State s = node.State

        \For {action in problem.Actions(s)}
        \State s' = problem.Result(s, action)
        \State cost = node.PathCost + problem.ActionCost(s, action, s')
        \State yield Node(State=s', Parent=node, Action=action, PathCost=cost)
        \EndFor
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[
            level distance=1.5cm,
            level 1/.style={sibling distance=5cm},
            level 2/.style={sibling distance=1.5cm},
            level 3/.style={sibling distance=1cm}
        ]
        \node[circle,draw,fill=green] {A}
        child {
                node[circle,draw,fill=gray] {S}
                child {node[circle,draw,fill=gray] {A}}
                child {node[circle,draw,fill=gray] {F}}
                child {node[circle,draw,fill=gray] {O}}
                child {node[circle,draw,fill=gray] {R}}
            }
        child {
                node[circle,draw,fill=gray] {T}
                child {node[circle,draw,fill=gray] {A}}
                child {node[circle,draw,fill=gray] {L}}
            }
        child {
                node[circle,draw,fill=gray] {Z}
                child {node[circle,draw,fill=gray] {A}}
                child {node[circle,draw,fill=gray] {O}}
            };
    \end{tikzpicture}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[
            level distance=1.5cm,
            level 1/.style={sibling distance=5cm},
            level 2/.style={sibling distance=1.5cm},
            level 3/.style={sibling distance=1cm}
        ]
        \node[circle,draw,fill=brown] {A}
        child {
                node[circle,draw,fill=red] {S}
                child {node[circle,draw,fill=gray] {A}}
                child {node[circle,draw,fill=gray] {F}}
                child {node[circle,draw,fill=gray] {O}}
                child {node[circle,draw,fill=gray] {R}}
            }
        child {
                node[circle,draw,fill=red] {T}
                child {node[circle,draw,fill=gray] {A}}
                child {node[circle,draw,fill=gray] {L}}
            }
        child {
                node[circle,draw,fill=red] {Z}
                child {node[circle,draw,fill=gray] {A}}
                child {node[circle,draw,fill=gray] {O}}
            };
    \end{tikzpicture}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[
            level distance=1.5cm,
            level 1/.style={sibling distance=5cm},
            level 2/.style={sibling distance=1.5cm},
            level 3/.style={sibling distance=1cm}
        ]
        \node[circle,draw,fill=brown] {A}
        child {
                node[circle,draw,fill=brown] {S}
                child {node[circle,draw,fill=red] {A}}
                child {node[circle,draw,fill=red] {F}}
                child {node[circle,draw,fill=red] {O}}
                child {node[circle,draw,fill=red] {R}}
            }
        child {
                node[circle,draw,fill=red] {T}
                child {node[circle,draw,fill=gray] {A}}
                child {node[circle,draw,fill=gray] {L}}
            }
        child {
                node[circle,draw,fill=red] {Z}
                child {node[circle,draw,fill=gray] {A}}
                child {node[circle,draw,fill=gray] {O}}
            };
    \end{tikzpicture}
\end{figure}

所有已经到达的结点（reached node）都保存在一个哈希表中，以便于避免重复搜索。\\

而所有前沿结点（frontier node）根据不同的搜索策略，可以使用栈、队列或优先队列保存，从而觉得后续需要扩展的结点。

\newpage

\section{盲目搜索策略}

\subsection{广度优先搜索（BFS, Breadth-First Search）}

\begin{figure}[H]
    \centering
    \includegraphics{img/Chapter1/1-4/1.png}
    \caption{BFS}
\end{figure}

BFS首先把从源点相邻的顶点遍历，然后再遍历稍微远一点的顶点，再去遍历更远一点的顶点。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[
            level distance=1.5cm,
            level 1/.style={sibling distance=4cm},
            level 2/.style={sibling distance=2cm},
            level 3/.style={sibling distance=1cm}
        ]
        \node[circle,draw] {1}
        child {
                node[circle,draw] {2}
                child {
                        node[circle,draw] {4}
                        child {node[circle,draw] {8}}
                        child {node[circle,draw] {9}}
                    }
                child {
                        node[circle,draw] {5}
                        child {node[circle,draw] {10}}
                        child {node[circle,draw] {11}}
                    }
            }
        child {
                node[circle,draw] {3}
                child {
                        node[circle,draw] {6}
                        child {node[circle,draw] {12}}
                        child {node[circle,draw] {13}}
                    }
                child {
                        node[circle,draw] {7}
                        child {node[circle,draw] {14}}
                        child {node[circle,draw] {15}}
                    }
            };
    \end{tikzpicture}
\end{figure}

\begin{algorithm}[H]
    \caption{BFS}
    \begin{algorithmic}[1]
        \Procedure{BFS}{problem} returns a solution node or failure
        \State node = Node(problem.Initial)

        \If {problem.IsGoal(node.State)}
        \State \Return node
        \EndIf
        \\
        \State frontier = Queue(node)
        \State reached = \{problem.Initial\}
        \\
        \While {not frontier.is\_empty()}
        \State node = frontier.dequeue()
        \For {child in Expand(problem, node)}
        \State s = child.State
        \If {problem.IsGoal(s)}
        \State \Return child
        \EndIf
        \If {s is not in reached}
        \State reached.add(s)
        \State frontier.enqueue(child)
        \EndIf
        \EndFor
        \EndWhile
        \\
        \State \Return failure
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\begin{itemize}
    \item 时间复杂度：$ O(b^d) $
    \item 空间复杂度：$ O(b^d) $（最多需要保存最后一层结点的数量）
    \item 完备性：YES（当$ d $有穷）
    \item 最优性：YES（总能找到最浅的目标结点）
\end{itemize}

\vspace{0.5cm}

\subsection{深度优先搜索（DFS, Depth-First Search）}

\begin{figure}[H]
    \centering
    \includegraphics{img/Chapter1/1-4/2.png}
    \caption{DFS}
\end{figure}

深度优先搜索是一种一头扎到底的遍历方法，选择一条路，尽可能不断地深入，遇到死路就回退，回退过程中如果遇到没探索的支路，就进入该支路继续深入。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \begin{scope}[every node/.style={circle,thick,draw}]
            \node (0) at (2.5,4) {0};
            \node (1) at (5,3) {1};
            \node (2) at (2.5,2) {2};
            \node (3) at (1,0) {3};
            \node (4) at (3,0) {4};
            \node (5) at (5,1) {5};
            \node (6) at (6,-1) {6};
            \node (7) at (0,3) {7};
        \end{scope}

        \begin{scope}[>={Stealth[black]},
            every node/.style={},
            every edge/.style={draw=black,very thick}]
            \path [-] (0) edge node {} (1);
            \path [-] (0) edge node {} (2);
            \path [-] (0) edge node {} (7);
            \path [-] (1) edge node {} (4);
            \path [-] (1) edge node {} (5);
            \path [-] (2) edge node {} (4);
            \path [-] (3) edge node {} (4);
            \path [-] (5) edge node {} (6);
        \end{scope}
    \end{tikzpicture}
\end{figure}

\begin{algorithm}[H]
    \caption{DFS}
    \begin{algorithmic}[1]
        \Procedure{DFS}{problem} returns a solution node or failure
        \State node = Node(problem.Initial)

        \If {problem.IsGoal(node.State)}
        \State \Return node
        \EndIf
        \\
        \State frontier = Stack(node)
        \\
        \While {not frontier.is\_empty()}
        \State node = frontier.pop()
        \If {problem.IsGoal(s)}
        \State \Return node
        \EndIf
        \\
        \If {not IsCycle(node)}
        \For {child in Expand(problem, node)}
        \State frontier.push(child)
        \EndFor
        \EndIf
        \EndWhile
        \\
        \State \Return failure
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\begin{itemize}
    \item 时间复杂度：$ O(b^m) $（当$ m $有穷）
    \item 空间复杂度：$ O(bm) $（只需要保存一层的兄弟结点）
    \item 完备性：NO（当$ m $无穷）
    \item 最优性：NO（只能找到最左解）
\end{itemize}

\vspace{0.5cm}

\subsection{深度限制搜索（DLS, Depth-Limit Search）}

DLS是DFS的变体，它限制了访问的深度。因为当树的子树过深时，进行DFS会在该子树上消耗太多的时间，所以在DLS中，若该结点的深度大于限制深度$ l $，那就不再继续遍历其子树了。\\

\begin{algorithm}[H]
    \caption{DLS}
    \begin{algorithmic}[1]
        \Procedure{DLS}{problem, l} returns a solution node or failure or cutoff
        \State frontier = Stack(problem.Initial)
        \State result = failure
        \\
        \While {not frontier.is\_empty()}
        \State node = frontier.pop()
        \If {Depth(node) > l}
        \State result = cutoff
        \ElsIf {not IsCycle(node)}
        \For {child in Expand(problem, node)}
        \State frontier.push(child)
        \EndFor
        \EndIf
        \EndWhile
        \\
        \State \Return result
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\begin{itemize}
    \item 时间复杂度：$ O(b^l) $
    \item 空间复杂度：$ O(bl) $
    \item 完备性：NO
    \item 最优性：NO
\end{itemize}

\vspace{0.5cm}

\subsection{迭代加深搜索（IDS, Iterative Deepening Search）}

IDS是DLS的升级版本，即首先允许深度优先搜索$ k $层搜索树，若没有发现可行解，再将$ k + 1 $后重复以上步骤搜索。\\

IDS将DFS的空间优势和BFS的时间优势结合起来，是一种比较好的搜索算法。\\

\begin{algorithm}[H]
    \caption{IDS}
    \begin{algorithmic}[1]
        \Procedure{IDS}{problem} returns a solution node or failure
        \For {depth = 0 to $ \infty $}
        \State result = DLS(problem, depth)
        \If {result != cutoff}
        \State \Return result
        \EndIf
        \EndFor
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\begin{itemize}
    \item 时间复杂度：$ O(b^d) $
    \item 空间复杂度：$ O(bd) $
    \item 完备性：YES
    \item 最优性：YES
\end{itemize}

\vspace{0.5cm}

IDS很明显存在重复的搜索，在迭代至第$ k $层时，会重复搜索前$ k - 1 $层的所有结点。虽然这的确浪费了一些时间，但是它并没有那么不堪。\\

假设分别计算使用BFS和IDS所生成的结点数量：

\vspace{-1cm}

\begin{align*}
    N(BFS) & = 1 + b^1 + b^2 + \cdots + b^d                    \\
    N(IDS) & = (d)b +  (d - 1)b^2 + (d-2)b^3 + \cdots + (1)b^d
\end{align*}

假设$ b = 10 $，$ d = 5 $时，$ N(BFS) = 111110 $，$ N(IDS) = 123450 $。可以计算得出IDS只比BFS多生成了11\%的结点。

\vspace{-1cm}

\begin{align*}
    {{N(IDS) - N(BFS)} \over {N(BFS)}} = 11\%
\end{align*}

因此，IDS只多生成了少量的结点，而节省了大量的空间。\\

\subsection{一致代价搜索（UCS, Uninformed-Cost Search）}

由于不同的行为具有不同的代价，每次选择一个从根结点到当前结点成本最低的路径是一个很好的选择。这被理论计算机科学界称为Dijkstra算法，被AI领域称为统一成本搜索UCS。BFS可以看作是根据树的深度一层一层扩展的，而UCS则是根据树的代价扩展的。\\

在罗马尼亚的部分地图中，问题是从Sibiu到达Bucharest。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \draw[fill=brown] (0,0) rectangle (0.3,0.3) node[above] {Fagaras};
        \draw[fill=brown] (-3,0) rectangle (-2.7,0.3) node[above] {Sibiu};
        \draw[fill=brown] (-2,-2) node[left] {Rimnicu Vilcea} rectangle (-1.7,-1.7);
        \draw[fill=brown] (0,-4) rectangle (0.3,-3.7) node[above] {Pitesti};
        \draw[fill=brown] (3,-5) node[left] {Bucharest} rectangle (3.3,-4.7);

        \draw[-] (0,0.15) -- (-1.35,0.15) node[above] {99} -- (-2.7,0.15);
        \draw[-] (-2.7,0) -- (-2,-1.7) node[xshift=-0.2cm, yshift=0.6cm, left] {80};
        \draw[-] (-1.8,-2) -- (0,-3.7) node[xshift=-1cm, yshift=0.8cm, below] {97};
        \draw[-] (0.3,-4) -- (3,-4.8) node[xshift=-1.5cm, yshift=0.5cm, below] {101};
        \draw[-] (3,-4.8) -- (0.3,0) node[xshift=1cm, yshift=-2cm, left] {211};
    \end{tikzpicture}
\end{figure}

Sibiu的后继结点是Rimnicu Vilcea和Fagaras，路径成本分别为$ 80 $和$ 99 $。因此扩展代价最低的结点Rimnicu Vilcea，计算得出到Pitesti的路径代价为$ 80 + 97 = 177 $。\\

其次路径代价最低的是Fagaras，计算得出到Bucharest的路径代价为$ 99 + 211 = 310 $。此时，虽然Bucharest是目标结点，但是UCS算法并不会在生成结点时判断其是否为目标结点，而是在扩展结点的时候判断。\\

因此算法会继续选择Pitesti进行扩展，计算得出到Bucharest的路径代价为$ 80 + 97 + 101 = 278 $。这个具有更小的路径代价，因此它替换之前到达这里的路径，并被添加到前沿结点集合中。最终，它在被扩展时发现是目标结点。\\

\begin{algorithm}[H]
    \caption{UCS}
    \begin{algorithmic}[1]
        \Procedure{UCS}{problem} returns a solution node or failure
        \State \Return BestFirstSearch(problem, PathCost)
        \EndProcedure
        \\
        \Procedure{BestFirstSearch}{problem, PathCost}
        \State node = Node(problem.Initial)
        \State frontier = PriorityQueue(node)   \# ordered by PathCost
        \State reached = \{problem.Initial: node\}
        \\
        \While {not frontier.is\_empty()}
        \State node = frontier.pop()
        \If {problem.IsGoal(node.State)}
        \State \Return node
        \EndIf
        \\
        \For {child in Expand(problem, node)}
        \State s = child.State
        \If {s is not in reached or child.PathCost < reached[s].PathCost}
        \State reached[s] = child
        \State frontier.push(child)
        \EndIf
        \EndFor
        \EndWhile
        \\
        \State \Return failure
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\begin{itemize}
    \item 时间复杂度：$ O(b^{1 + \lfloor C^* / \epsilon \rfloor}) $
    \item 空间复杂度：$ O(b^{1 + \lfloor C^* / \epsilon \rfloor}) $
    \item 完备性：YES
    \item 最优性：YES
\end{itemize}

\newpage

\section{启发式搜索}

\subsection{启发式搜索（Informed Search）}

盲目搜索只使用问题中提供的信息（如路径代价），而启发式搜索使用额外的信息（如估计值），通过指导向最有希望的方向前进，从而达到减少搜索范围、降低问题复杂度。\\

然而，启发式策略是极易出错的。在解决问题的过程中启发仅仅是下一步将要采取措施的一个猜想，常常根据经验和直觉来判断。启发式函数$ h(n) $（heuristic function）用于表示结点$ n $到达目标结点的最小估计代价。\\

例如在八数码问题中，可以根据处于错误位置的数字的数量来作为引导。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \draw (-1,10) rectangle (1,12);
        \draw[-] (-1,10.666) -- (1,10.666);
        \draw[-] (-1,11.333) -- (1,11.333);
        \draw[-] (-0.333,10) -- (-0.333,12);
        \draw[-] (0.333,10) -- (0.333,12);
        \node at (-0.666,11.666) {1};
        \node at (0,11.666) {2};
        \node at (0.666,11.666) {3};
        \node at (-0.666,11) {4};
        \node at (0.666,11) {5};
        \node at (-0.666,10.333) {7};
        \node at (0,10.333) {8};
        \node at (0.666,10.333) {6};

        \draw (-7,6) rectangle (-5,8);
        \draw[-] (-7,6.666) -- (-5,6.666);
        \draw[-] (-7,7.333) -- (-5,7.333);
        \draw[-] (-6.333,6) -- (-6.333,8);
        \draw[-] (-5.666,6) -- (-5.666,8);
        \node at (-6.666,7.666) {1};
        \node at (-6,7.666) {2};
        \node at (-5.333,7.666) {3};
        \node at (-6,7) {4};
        \node at (-5.333,7) {5};
        \node at (-6.666,6.333) {7};
        \node at (-6,6.333) {8};
        \node at (-5.333,6.333) {6};

        \draw (-3,6) rectangle (-1,8);
        \draw[-] (-3,6.666) -- (-1,6.666);
        \draw[-] (-3,7.333) -- (-1,7.333);
        \draw[-] (-2.333,6) -- (-2.333,8);
        \draw[-] (-1.666,6) -- (-1.666,8);
        \node at (-2.666,7.666) {1};
        \node at (-2,7.666) {2};
        \node at (-1.333,7.666) {3};
        \node at (-2.666,7) {4};
        \node at (-2,7) {5};
        \node at (-2.666,6.333) {7};
        \node at (-2,6.333) {8};
        \node at (-1.333,6.333) {6};

        \draw (1,6) rectangle (3,8);
        \draw[-] (3,6.666) -- (1,6.666);
        \draw[-] (3,7.333) -- (1,7.333);
        \draw[-] (2.333,6) -- (2.333,8);
        \draw[-] (1.666,6) -- (1.666,8);
        \node at (1.333,7.666) {1};
        \node at (2.666,7.666) {3};
        \node at (1.333,7) {4};
        \node at (2,7) {2};
        \node at (2.666,7) {5};
        \node at (1.333,6.333) {7};
        \node at (2,6.333) {8};
        \node at (2.666,6.333) {6};

        \draw (7,6) rectangle (5,8);
        \draw[-] (7,6.666) -- (5,6.666);
        \draw[-] (7,7.333) -- (5,7.333);
        \draw[-] (6.333,6) -- (6.333,8);
        \draw[-] (5.666,6) -- (5.666,8);
        \node at (5.333,7.666) {1};
        \node at (6,7.666) {2};
        \node at (6.666,7.666) {3};
        \node at (5.333,7) {4};
        \node at (6,7) {8};
        \node at (6.666,7) {5};
        \node at (5.333,6.333) {7};
        \node at (6.666,6.333) {6};

        \draw (-5,2) rectangle (-3,4);
        \draw[-] (-5,2.666) -- (-3,2.666);
        \draw[-] (-5,3.333) -- (-3,3.333);
        \draw[-] (-4.333,2) -- (-4.333,4);
        \draw[-] (-3.666,2) -- (-3.666,4);
        \node at (-4.666,3.666) {1};
        \node at (-4,3.666) {2};
        \node at (-3.333,3.666) {3};
        \node at (-4.666,3) {4};
        \node at (-3.333,3) {5};
        \node at (-4.666,2.333) {7};
        \node at (-4,2.333) {8};
        \node at (-3.333,2.333) {6};

        \draw (-1,2) rectangle (1,4);
        \draw[-] (-1,2.666) -- (1,2.666);
        \draw[-] (-1,3.333) -- (1,3.333);
        \draw[-] (-0.333,2) -- (-0.333,4);
        \draw[-] (0.333,2) -- (0.333,4);
        \node at (-0.666,3.666) {1};
        \node at (0,3.666) {2};
        \node at (-0.666,3) {4};
        \node at (0,3) {5};
        \node at (0.666,3) {3};
        \node at (-0.666,2.333) {7};
        \node at (0,2.333) {8};
        \node at (0.666,2.333) {6};

        \draw (3,2) rectangle (5,4);
        \draw[-] (3,2.666) -- (5,2.666);
        \draw[-] (3,3.333) -- (5,3.333);
        \draw[-] (4.333,2) -- (4.333,4);
        \draw[-] (3.666,2) -- (3.666,4);
        \node at (3.333,3.666) {1};
        \node at (4,3.666) {2};
        \node at (4.666,3.666) {3};
        \node at (3.333,3) {4};
        \node at (4,3) {5};
        \node at (4.666,3) {6};
        \node at (3.333,2.333) {7};
        \node at (4,2.333) {8};

        \draw (0,10) -- (-6,8);
        \draw (0,10) -- (-2,8);
        \draw (0,10) -- (2,8);
        \draw (0,10) -- (6,8);
        \node at (-4,9) {Left};
        \node at (-1.8,9) {Right};
        \node at (1.8,9) {Up};
        \node at (4,9) {Down};
        \node at (-6,5.7) {$ h = 3 $};
        \node at (-3.7,5.7) {$ h = 1 $};
        \node at (2,5.7) {$ h = 3 $};
        \node at (6,5.7) {$ h = 4 $};

        \draw (-2,6) -- (-4,4);
        \draw (-2,6) -- (0,4);
        \draw (-2,6) -- (4,4);
        \node at (-4,5) {Left};
        \node at (-1.8,5) {Up};
        \node at (1.8,5) {Down};
    \end{tikzpicture}
\end{figure}

\vspace{0.5cm}

\subsection{贪婪最佳优先搜索（Greedy Best-First Search）}

所谓贪婪，即只扩展当前代价最小的结点。但是贪心搜索不能保证最优，甚至都不能保证完备，因为它可能陷入死循环。\\

贪心只根据启发进行搜索，即评估函数$ f(n) = h(n) $。\\

假设$ h(n) $是当前城市到Bucharest的直线距离，这个直线距离是原问题所不具备的。

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \draw[fill=brown] (0,0) rectangle (0.3,0.3) node[above] {Fagaras};
        \draw[fill=brown] (-3,0) rectangle (-2.7,0.3) node[above] {Sibiu};
        \draw[fill=brown] (-2,-2) node[left] {Rimnicu Vilcea} rectangle (-1.7,-1.7);
        \draw[fill=brown] (0,-4) rectangle (0.3,-3.7) node[above] {Pitesti};
        \draw[fill=brown] (3,-5) node[left] {Bucharest} rectangle (3.3,-4.7);

        \draw[-] (0,0.15) -- (-1.35,0.15) node[above] {99} -- (-2.7,0.15);
        \draw[-] (-2.7,0) -- (-2,-1.7) node[xshift=-0.2cm, yshift=0.6cm, left] {80};
        \draw[-] (-1.8,-2) -- (0,-3.7) node[xshift=-1cm, yshift=0.8cm, below] {97};
        \draw[-] (0.3,-4) -- (3,-4.8) node[xshift=-1.5cm, yshift=0.5cm, below] {101};
        \draw[-] (3,-4.8) -- (0.3,0) node[xshift=1cm, yshift=-2cm, left] {211};
    \end{tikzpicture}
\end{figure}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|}
            \hline
            Bucharest      & 0   \\
            \hline
            Fagaras        & 176 \\
            \hline
            Pitesti        & 100 \\
            \hline
            Rimnicu Vilcea & 193 \\
            \hline
            Sibiu          & 253 \\
            \hline
        \end{tabular}
    }
    \caption{各个城市到Bucharest的直线距离}
\end{table}

问题是从Sibiu到Bucharest，GBFS算法的搜索过程如下：

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{4mm}{
        \begin{tabular}{|c|c|c|l|l|}
            \hline
            \textbf{Node} & \textbf{IsGoal(Node)} & \textbf{s}  & \textbf{Frontier}      & \textbf{Reached}                     \\
            \hline
            $ S $         & NO                    &             & [$ S_{253} $]          & \{$ S_0 $\}                          \\
            \hline
            $ S $         & NO                    & $ R_{193} $ & [$ R_{193} $]          & \{$ S_0, R_{80} $\}                  \\
            \hline
            $ S $         & NO                    & $ F_{176} $ & [$ R_{193}, F_{176} $] & \{$ S_0, R_{80}, F_{99} $\}          \\
            \hline
            $ F $         & NO                    & $ B_0 $     & [$ R_{193}, B_0 $]     & \{$ S_0, R_{80}, F_{99}, B_0 $\}     \\
            \hline
            $ F $         & NO                    & $ S_{253} $ & [$ R_{193}, B_0 $]     & \{$ S_0, R_{80}, F_{99}, P_{177} $\} \\
            \hline
            $ B $         & YES                   &             &                        &                                      \\
            \hline
        \end{tabular}
    }
\end{table}

\begin{algorithm}[H]
    \caption{GBFS}
    \begin{algorithmic}[1]
        \Procedure{GBFS}{problem, f} returns a solution node or failure
        \State node = Node(problem.Initial)
        \State frontier = PriorityQueue(node)   \# ordered by f
        \State reached = \{problem.Initial: node\}
        \\
        \While {not frontier.is\_empty()}
        \State node = frontier.pop()
        \If {problem.IsGoal(node.State)}
        \State \Return node
        \EndIf
        \\
        \For {child in Expand(problem, node)}
        \State s = child.State
        \If {s is not in reached or child.PathCost < reached[s].PathCost}
        \State reached[s] = child
        \State frontier.push(child)
        \EndIf
        \EndFor
        \EndWhile
        \\
        \State \Return failure
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\vspace{0.5cm}

\subsection{A*搜索（A* Search）}

A*搜索的评估函数为$ f(n) = g(n) + h(h) $，其中$ g(n) $是从初始结点到结点$ n $的实际代价，$ h(n) $是从结点$ n $到达目标结点的最小估计代价。\\

启发函数会影响A*搜索的性能。在极端情况下，当$ h(n) = 0 $，则$ g(n) $将决定结点的优先级，此时算法就退化成了UCS。\\

当$ h(n) $始终小于等于结点$ n $到目标结点的实际代价$ h^*(n) $，A*算法保证一定能够找到最短路径。但是$ h(n) $的值越小，算法将遍历越多的结点，导致算法越慢。\\

当$ h(n) $完全等于$ h^*(n) $时，A*算法将很快速地找到最佳路径。可惜并非所有场景下都能做到这一点，因为在到达终点之前，很难确切地算出距离终点的距离。\\

当$ h(n) $远大于$ g(n) $时，此时只有$ h(n) $产生效果，算法也就变成了GBFS。\\

A*算法对于部分罗马尼亚地图的搜索过程如下：

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{0.5mm}{
        \begin{tabular}{|c|c|c|l|l|}
            \hline
            \textbf{Node}   & \textbf{IsGoal} & \textbf{s}      & \textbf{Frontier}             & \textbf{Reached}                                                  \\
            \hline
            $ S_{0+253} $   & NO              &                 & [$ S_{0+253} $]               & \{$ S_{0+253} $\}                                                 \\
            \hline
            $ S_{0+253} $   & NO              & $ R_{80+193} $  & [$ R_{80+193} $]              & \{$ S_{0+253}, R_{80+193} $\}                                     \\
            \hline
            $ S_{0+253} $   & NO              & $ F_{99+176} $  & [$ R_{80+193}, F_{99+176} $]  & \{$ S_{0+253}, R_{80+193}, F_{99+176} $\}                         \\
            \hline
            $ R_{80+193} $  & NO              & $ P_{177+100} $ & [$ F_{99+176}, P_{177+100} $] & \{$ S_{0+253}, R_{80+193}, F_{99+176}, P_{177+100} $\}            \\
            \hline
            $ R_{80+193} $  & NO              & $ S_{160+253} $ & [$ F_{99+176}, P_{177+100} $] & \{$ S_{0+253}, R_{80+193}, F_{99+176}, P_{177+100} $\}            \\
            \hline
            $ F_{99+176} $  & NO              & $ B_{310+0} $   & [$ P_{177+100}, B_{310+0} $]  & \{$ S_{0+253}, R_{80+193}, F_{99+176}, P_{177+100}, B_{310+0} $\} \\
            \hline
            $ F_{99+176} $  & NO              & $ S_{198+253} $ & [$ P_{177+100}, B_{310+0} $]  & \{$ S_{0+253}, R_{80+193}, F_{99+176}, P_{177+100}, B_{310+0} $\} \\
            \hline
            $ P_{177+100} $ & NO              & $ B_{278+0} $   & [$ B_{310+0}, B_{278+0} $]    & \{$ S_{0+253}, R_{80+193}, F_{99+176}, P_{177+100}, B_{278+0} $\} \\
            \hline
            $ B_{278+0} $   & YES             &                 &                               &                                                                   \\
            \hline
        \end{tabular}
    }
\end{table}

\newpage

\section{局部搜索}

\subsection{局部搜索（Local Search）}

局部搜索是一种用于解决计算上难以优化的问题（如NP问题）的启发式方法。算法每次从当前解的邻域解空间中选择一个最好邻居作为下次迭代的当前解，直到达到一个局部最优解。\\

传统的N皇后问题使用的是回溯法（backtrack）解决的，但是一旦问题的规模过大，计算时间复杂度是不能够接受的。\\

\subsection{爬山法（Hill Climbing）}

设想去攀登一座山群的最高峰，而此山群有很多的小山峰，且我们对此山群一无所知。那么当我们来到一座小山峰（局部极值点）时，我们会错误地判断这就是最高峰，事实上这有可能是一个很糟糕的解（即与最高峰还差很远）。\\

\begin{figure}[H]
    \centering
    \includegraphics{img/Chapter1/1-6/1.png}
\end{figure}

\begin{algorithm}[H]
    \caption{HillClimbing}
    \begin{algorithmic}[1]
        \Procedure{HillClimbing}{problem} returns a state that is a local maximum
        \State current = problem.Initial
        \While {true}
        \State neighbor = a highest-valued successor state of current
        \If {Value(neighbor) <= Value(current)}
        \State \Return current
        \EndIf
        \State current = neighbor
        \EndWhile
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

爬山法解决N皇后问题时，利用评估函数（导致皇后冲突的对数）来评估皇后摆放位置的好坏。\\

例如对于4皇后，初始状况皇后都位于第1行中，皇后可以被移动到每列的任意位置上。\\

爬山法对每个皇后能够移动的位置进行评估，例如-4代表该列的皇后移到到该位置后，会有4对皇后产生冲突。

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \draw[step=1cm,color=gray] (-2,-2) grid (2,2);
        \matrix[matrix of nodes,nodes={inner sep=0pt,text width=1cm,align=center,minimum height=1cm}]{
            \symqueen & \symqueen & \symqueen & \symqueen                  \\
            -4        & -5        & -5        & -4                         \\
            -4        & -4        & -4        & -4                         \\
            -4        & -3        & -3        & -4\\};
    \end{tikzpicture}
\end{figure}

依次选择评估值最大的位置，将对应列的皇后移到该位置。

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \draw[step=1cm,color=gray] (-2,-2) grid (2,2);
        \matrix[matrix of nodes,nodes={inner sep=0pt,text width=1cm,align=center,minimum height=1cm}]{
            \symqueen & -6        & \symqueen & \symqueen                  \\
            -1        & -5        & -2        & -3                         \\
            -3        & -4        & -3        & -1                         \\
            -3        & \symqueen & -2        & -3\\};
    \end{tikzpicture}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \draw[step=1cm,color=gray] (-2,-2) grid (2,2);
        \matrix[matrix of nodes,nodes={inner sep=0pt,text width=1cm,align=center,minimum height=1cm}]{
                      &           & \symqueen & \symqueen                \\
            \symqueen &           &           &                          \\
                      &           &           & 0                        \\
                      & \symqueen &           & \\};
    \end{tikzpicture}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \draw[step=1cm,color=gray] (-2,-2) grid (2,2);
        \matrix[matrix of nodes,nodes={inner sep=0pt,text width=1cm,align=center,minimum height=1cm}]{
                      &           & \symqueen &                          \\
            \symqueen &           &           &                          \\
                      &           &           & \symqueen                \\
                      & \symqueen &           & \\};
    \end{tikzpicture}
\end{figure}

爬山法还有很多变体：

\begin{itemize}
    \item 随机爬山法（Stochastic Hill-Climbing）：随机选择比当前结点更优的后继结点。
    \item 首选爬山法（First-Choice Hill-Climbing）：选择第一个比当前结点更优的后继结点。
    \item 随机重新开始爬山法（Random Restart Hill-Climbing）：通过随机生成的初始状态来进行一系列的爬山法搜索，找到目标时停止搜索。
\end{itemize}

\vspace{0.5cm}

\subsection{模拟退火（Simulated Annealing）}

模拟退火是一个由金属退火启发的算法。在物理应用中分子排布可能是紊乱的，如果我们将它升温然后缓慢降温，就可以生成完美的晶形。\\

\begin{figure}[H]
    \centering
    \includegraphics{img/Chapter1/1-6/2.png}
    \caption{物理退火}
\end{figure}

模拟退火算法也是一种局部搜索算法，它的思想是在初始状态下，随机生成一个解，然后在解的邻域中随机选择一个解，如果该解比当前解更好，就接受该解，否则以一定的概率接受该解。\\

例如在计算最小值的问题中，如果新解比当前解更小，就接受该解，否则以一定的概率接受该解，这个概率随着温度的降低而减小。

\vspace{-1cm}

\begin{align*}
     & \Delta E = Value(current) - Value(next)
\end{align*}

\begin{enumerate}
    \item 如果$ \Delta E > 0 $：以概率为1接受新解
    \item 否则：以概率为$ e^{\Delta E \over T} $接受新解
\end{enumerate}

其中$ T $表示温度，会随着时间（算法的迭代）逐渐降低。接受解的概率会因$ T $受到影响：

\vspace{-1cm}

\begin{align*}
    \lim_{T \rightarrow \infty} P(\text{Acceptance of bad move}) & = 1 \\
    \lim_{T \rightarrow 0} P(\text{Acceptance of bad move})      & = 0
\end{align*}

\begin{algorithm}[H]
    \caption{SimulatedAnnealing}
    \begin{algorithmic}[1]
        \Procedure{SimulatedAnnealing}{problem, schedule} returns a solution state
        \State current = problem.Initial
        \For {t = 1 to $ \infty $}
        \State T = schedule(t)
        \If {T = 0}
        \State \Return current
        \EndIf
        \\
        \State next = problem.RandomSuccessor(current)
        \State $ \Delta E $ = Value(current) - Value(next)
        \If {$ \Delta E $ > 0}
        \State current = next
        \Else
        \State current = next with probability $ e^{\Delta E \over T} $
        \EndIf
        \EndFor
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\newpage